package Sort;

public class Sort {
    /**
     * 时间复杂度 O(N^2)
     * 最坏情况下：逆序的： 5 4 3 2 1
     * 最好情况下：有序的：1 2 3 4 5 O（N）
     * 如果数据越有序，直接插入排序越快
     * 空间复杂度 ： O(1)
     * 稳定性：稳定的排序
     * 本身如果是一个稳定的排序，那么可以实现为不稳定的
     * 但是，如果一个排序 本身就是不稳定的，能实现为稳定的吗？  不能
     * @param arr
     */
    public  static  void insetSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp =arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1] =arr[j];
                }else{
                    arr[j+1] =tmp;
                    break;;
                }
            }
            arr[j+1]  = tmp;
        }

    }
}
